package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.list.singly.ListNode;

/**
 * @author qidi
 * @date 2022-01-17 11:40:27
 */
class Q0142_LinkedListCycleIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null || head.next == null || head.next.next == null) return null;

            ListNode slow = head, fast = head;

            while (fast != null) {
                slow = slow.next;
                if (fast.next == null) return null;
                fast = fast.next.next;
                if (slow != null && fast != null && slow == fast) {
                    // 相遇
                    fast = head;
                    while (true) {
                        // 第二次相遇
                        if (fast == slow) return fast;
                        fast = fast.next;
                        slow = slow.next;
                    }
                }
            }

            return null;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0142_LinkedListCycleIi().new Solution();
    }
}